//Given a string num that contains only digits and an integer target, return all
// possibilities to insert the binary operators '+', '-', and/or '*' between the d
//igits of num so that the resultant expression evaluates to the target value. 
//
// Note that operands in the returned expressions should not contain leading zer
//os. 
//
// 
// Example 1: 
//
// 
//Input: num = "123", target = 6
//Output: ["1*2*3","1+2+3"]
//Explanation: Both "1*2*3" and "1+2+3" evaluate to 6.
// 
//
// Example 2: 
//
// 
//Input: num = "232", target = 8
//Output: ["2*3+2","2+3*2"]
//Explanation: Both "2*3+2" and "2+3*2" evaluate to 8.
// 
//
// Example 3: 
//
// 
//Input: num = "105", target = 5
//Output: ["1*0+5","10-5"]
//Explanation: Both "1*0+5" and "10-5" evaluate to 5.
//Note that "1-05" is not a valid expression because the 5 has a leading zero.
// 
//
// Example 4: 
//
// 
//Input: num = "00", target = 0
//Output: ["0*0","0+0","0-0"]
//Explanation: "0*0", "0+0", and "0-0" all evaluate to 0.
//Note that "00" is not a valid expression because the 0 has a leading zero.
// 
//
// Example 5: 
//
// 
//Input: num = "3456237490", target = 9191
//Output: []
//Explanation: There are no expressions that can be created from "3456237490" to
// evaluate to 9191.
// 
//
// 
// Constraints: 
//
// 
// 1 <= num.length <= 10 
// num consists of only digits. 
// -231 <= target <= 231 - 1 
// 
// Related Topics 数学 字符串 回溯 
// 👍 251 👎 0


package leetcode.editor.cn;

import java.util.ArrayList;
import java.util.List;

//Java：Expression Add Operators
class P282ExpressionAddOperators {
    public static void main(String[] args) {
        Solution solution = new P282ExpressionAddOperators().new Solution();
        // TO TEST
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public List<String> addOperators(String num, int target) {
            List<String> ans = new ArrayList<>();
            char[] expr = new char[2 * num.length()];
            dfs(num, expr, 0, 0, 0, 0, target, ans);
            return ans;
        }

        public void dfs(String num, char[] expr, int len, long prevValue, long currValue, int pos, int target, List<String> res) {
            if (pos == num.length()) {
                if (currValue == target) {
                    res.add(new String(expr, 0, len));
                }
                return;
            }
            long n = 0; // 避免溢出
            int s = pos; // 保留初始位置，出栈时恢复使用
            int l = len; // 保留原始长度，出栈时恢复使用
            if (s != 0) {
                ++len;
            }
            while (pos < num.length()) {
                n = n * 10 + num.charAt(pos) - '0';
                if (num.charAt(s) == '0' && pos - s > 0) { // 消除0xx数字
                    break;
                }
                if (n > Integer.MAX_VALUE) {
                    break;
                }
                expr[len] = num.charAt(pos);
                len++;
                pos++;
                if (s == 0) {
                    dfs(num, expr, len, n, n, pos, target, res);
                    continue;
                }
                expr[l] = '+';
                dfs(num, expr, len, n, currValue + n, pos, target, res);
                expr[l] = '-';
                dfs(num, expr, len, -n, currValue - n, pos, target, res);
                expr[l] = '*';
                dfs(num, expr, len, prevValue * n, currValue - prevValue + prevValue * n, pos, target, res);
            }
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}